|
|
Použití programování s omezujícími podmínkami při řešení diskrétních úloh
Janečková, Jitka ; Fábry, Jan (vedoucí práce) ; Černý, Michal (oponent)
Použití programování s omezujícími podmínkami (CP) je jedním z možných způsobů řešení diskrétních úloh. Lze ho použít jak k hledání přípustného řešení, tak k optimalizaci. CP nabízí celou řadu metod určených buď k samotnému nalezení řešení nebo ke zrychlení procesu jeho hledání -- od prohledávacích algoritmů přes konzistenční techniky po propagační techniky, které jsou vlastně jen kombinací předchozích dvou. K optimalizaci se nejčastěji používá metoda větvení a mezí, která se v některých aspektech odlišuje od stejnojmenné metody matematického programování (MP). Porovnání CP s MP je zajímavé i v dalších ohledech. CP například vyniká ve flexibilnější formulaci úloh, která umožňuje vytvořit často jednodušší a menší model. Naopak jeho nevýhodou je omezené použití: Problém (optimálního) splňování podmínek, jak úlohu programování s omezujícími podmínkami nazýváme, nesmí obsahovat spojité proměnné. Vhodné je pak především pro úlohy obsahující hodně omezení, které mají málo proměnných, nejlépe pouze dvě. Práce seznámí čtenáře se základními pojmy programování s omezujícími podmínkami, především se ale zabývá popisem algoritmů a technik používaných k řešení diskrétních úloh a porovnáním CP s matematickým programováním.
|
host ::
RSS.